/**
位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-median-from-data-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
type MedianFinder struct {
    Big  *IntMaxHeap
    Small *IntMinHeap
}


/** initialize your data structure here. */
func Constructor() MedianFinder {
    return MedianFinder{
        Big:&IntMaxHeap{},
        Small:&IntMinHeap{},
    }
}


func (this *MedianFinder) AddNum(num int)  {
    heap.Push(this.Small,num)
    heap.Push(this.Big,heap.Pop(this.Small))
    if this.Big.Len() > this.Small.Len(){
        heap.Push(this.Small,heap.Pop(this.Big))
    }
}


func (this *MedianFinder) FindMedian() float64 {
    if this.Small.Len() > this.Big.Len(){
        return float64((*this.Small)[0])
    }else{
        return (float64((*this.Small)[0]) + float64((*this.Big)[0])) / 2.0
    }
}
type IntMaxHeap []int
type IntMinHeap []int

func (h IntMaxHeap) Len() int {
    return len(h)
}
func (h IntMinHeap) Len() int {
    return len(h)
}
func (h IntMaxHeap) Less(i int, j int) bool {
    return h[i] >= h[j]
}
func (h IntMinHeap) Less(i int, j int) bool {
    return h[i] <= h[j]
}
func (h IntMaxHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h IntMinHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntMaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntMinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntMaxHeap) Pop() interface{} {
    length := len(*h)
    val := (*h)[length - 1]
    *h = (*h)[: length - 1]

    return val
}
func (h *IntMinHeap) Pop() interface{} {
    length := len(*h)
    val := (*h)[length - 1]
    *h = (*h)[: length - 1]
    return val
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */